// Copyright (c) 2023 刻BITTER
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.


#pragma once

#include <cstdint>
#include <cstdlib>

#include "./common.hpp"

namespace data_basic {

    /**
     * @brief 双向链表节点
     *
     * @tparam NodeDataType
     */
    template <typename T>
    struct LinkNode {
        using DataType = T;

        LinkNode *next;
        LinkNode *prev;
        T data;
    };


    /**
     * @brief 单向链表节点
     *
     * @tparam NodeDataType
     */
    template <typename T>
    struct ForwardLinkNode {
        using DataType = T;

        ForwardLinkNode *forward;  // 单向链表和双向链表使用不同的指针名称，可以用来实现混合节点，让一个节点同时位于双向和单向链表中
        T data;
    };


    template <typename T>
    struct DoubleLinkNode {
        using DataType = T;

        // 用于单向链表
        DoubleLinkNode *forward;

        // 用于双向链表
        DoubleLinkNode *next;
        DoubleLinkNode *prev;

        T data;
    };


    template <typename _NodeType>
    class ForwardLink {
       public:
        using NodeType = _NodeType;
        using DataType = typename NodeType::DataType;


       private:
        NodeType *_front = nullptr;
        NodeType *_back = nullptr;

       public:
        bool empty() const { return this->_front == nullptr; }

        NodeType *front() { return _front; }

        const NodeType *front() const { return _front; }

        NodeType *back() { return _back; }

        const NodeType *back() const { return _back; }

        NodeType *pop_front() {
            if (_front == nullptr) {
                return nullptr;
            }
            else {
                NodeType *n = _front;
                _front = _front->forward;

                if (_front == nullptr) {  // 链表最后一个节点被弹出，_back 指针也设为nullptr
                    _back = nullptr;
                }

                return n;
            }
        }

        /**
         * @brief 在头部插入节点
         *
         * push_front 和pop_front 配合，可实现LIFO，也就是栈
         *
         * @param new_node
         */
        void push_front(NodeType *new_node) {
            new_node->forward = _front;

            if (_front == nullptr) {  // 如果是空的链表，让back 也指向第一个节点
                _back = new_node;
            }

            _front = new_node;
        }

        /**
         * @brief 在尾部插入节点
         *
         * push_back 和pop_front 配合，可实现FIFO，也就是队列
         *
         * @param new_node
         */
        void push_back(NodeType *new_node) {
            new_node->forward = nullptr;

            // 如果链表为空，让_front 也指向新节点，否则，要让原来的尾部节点指向新节点
            if (_front == nullptr) {
                _front = new_node;
            }
            else {
                _back->forward = new_node;
            }

            _back = new_node;
        }


        /**
         * @brief 清空链表
         *
         */
        void clear() {
            _front = nullptr;
            _back = nullptr;
        }


        void insert_after(NodeType *new_node, NodeType *prev) {
            if (prev == nullptr) {
                // 插入位置在链表头部，或链表为空
                push_front(new_node);
            }
            else if (prev == _back) {
                // 插入位置在链表尾部
                push_back(new_node);
            }
            else {
                // 在中间插入，不影响_front 和_back 指针
                new_node->forward = prev->forward;
                prev->forward = new_node;
            }
        }


        /**
         * @brief 按节点内data 的大小，将新节点插入到大于等于该节点的其他节点前面
         *
         * DataType 要支持operator < 。
         * 自始至终只使用 insert_sorted 插入元素，可保证链表从小到大顺序，否则结果随机
         *
         * @param new_node
         * @return NodeType* 返回新节点的前一个节点。若为nullptr，表示新节点在链表头部
         */
        NodeType *insert_sorted(NodeType *new_node) {
            NodeType *current = this->_front;
            NodeType *prev = nullptr;

            // 查找插入位置
            while (current != nullptr && current->data < new_node->data) {  // 找到一个比新节点大的节点，把新节点插在前面，实现从小到大排序
                prev = current;
                current = current->forward;
            }

            insert_after(new_node, prev);
            return prev;
        }
    };


    template <typename _NodeType>
    class DoubleLink {
       public:
        using NodeType = _NodeType;
        using DataType = typename NodeType::DataType;

       private:
        NodeType *_front = nullptr;
        NodeType *_back = nullptr;

       public:
        bool empty() const { return this->_front == nullptr; }

        NodeType *front() { return _front; }

        const NodeType *front() const { return _front; }

        NodeType *back() { return _back; }

        const NodeType *back() const { return _back; }

        NodeType *pop_front() {
            if (_front == nullptr) {
                return nullptr;
            }
            else {
                NodeType *n = _front;
                _front = _front->next;

                if (_front == nullptr) {  // 链表最后一个节点被弹出，_back 指针也设为nullptr
                    _back = nullptr;
                }

                return n;
            }
        }

        /**
         * @brief 在头部插入节点
         *
         * push_front 和pop_front 配合，可实现LIFO，也就是栈
         *
         * @param new_node
         */
        void push_front(NodeType *new_node) {
            new_node->next = _front;
            new_node->prev = nullptr;

            if (_front == nullptr) {  // 如果是空的链表，让back 也指向第一个节点
                _back = new_node;
            }

            _front = new_node;
        }

        NodeType *pop_back() {
            if (_front == nullptr) {
                return nullptr;
            }
            else {
                NodeType *n = _back;
                _back = _back->prev;

                if (_back == nullptr) {  // 链表最后一个节点被弹出，_front 指针也设为nullptr
                    _front = nullptr;
                }

                return n;
            }
        }

        /**
         * @brief 在尾部插入节点
         *
         * push_back 和pop_front 配合，可实现FIFO，也就是队列
         *
         * @param new_node
         */
        void push_back(NodeType *new_node) {
            new_node->next = nullptr;

            // 如果链表为空，让_front 也指向新节点，否则，要让原来的尾部节点指向新节点
            if (_front == nullptr) {
                _front = new_node;
            }
            else {
                _back->next = new_node;
                new_node->prev = _back;
            }

            _back = new_node;
        }

        void remove(NodeType *target) {
            auto *n = target->next;
            auto *p = target->prev;

            if (p == nullptr) {  // 约定头部节点prev == nullptr, 尾部节点next == nullptr
                _front = n;
                _front->prev = nullptr;
            }
            else if (n == nullptr) {
                _back = p;
                _back->next = nullptr;
            }
            else {
                p->next = n;
                n->prev = p;
            }
        }

        /**
         * @brief 清空链表
         *
         */
        void clear() {
            _front = nullptr;
            _back = nullptr;
        }

        void insert_after(NodeType *new_node, NodeType *prev) {
            if (prev == nullptr) {
                // 插入位置在链表头部，或链表为空
                push_front(new_node);
            }
            else if (prev == _back) {
                // 插入位置在链表尾部
                push_back(new_node);
            }
            else {
                // 在中间插入，不影响_front 和_back 指针
                new_node->prev = prev;
                new_node->next = prev->next;
                prev->next = new_node;
                prev->next->prev = new_node;
            }
        }

        /**
         * @brief 按节点内data 的大小，将新节点插入到大于等于该节点的其他节点前面
         *
         * DataType 要支持operator < 。
         * 自始至终只使用 insert_sorted 插入元素，可保证链表从小到大顺序，否则结果随机
         *
         * @param new_node
         * @return NodeType* 返回新节点的前一个节点。若为nullptr，表示新节点在链表头部
         */
        NodeType *insert_sorted(NodeType *new_node) {
            NodeType *current = this->_front;
            NodeType *prev = nullptr;

            // 查找插入位置
            while (current != nullptr && current->data < new_node->data) {  // 找到一个比新节点大的节点，把新节点插在前面，实现从小到大排序
                prev = current;
                current = current->forward;
            }

            insert_after(new_node, prev);
            return prev;
        }
    };


}  // namespace data_basic
